package own.stu.jobgib.playown.alg.leetcode.editor.cn.demo;

import org.activiti.engine.impl.bpmn.behavior.UserTaskActivityBehavior;
import own.stu.jobgib.playown.alg.leetcode.editor.cn.ListNode;

import java.util.*;
import java.util.stream.Collectors;

public class Demo {
    public static void main(String[] args) {
        Station a = new Station("a", 30);
        Station b = new Station("b", 40);
        Station c = new Station("c", 40);

//        Truck t1 = new Truck();
//        System.out.println(minSubArrayLen(7, new int[]{2, 3, 1, 2, 4, 3}));
//        System.out.println(minSubArrayLen(4, new int[]{1, 4, 4}));
//        System.out.println(minSubArrayLen(11, new int[]{1, 1, 1, 1, 1, 1, 1, 1}));

//        System.out.println(mergeAlternately("ab", "cd"));
//        System.out.println(mergeAlternately("abxx", "cd"));
//        System.out.println(mergeAlternately("ab", "cdyyy"));

//        System.out.println(findTheDifference("abcd", "abcde"));
//        System.out.println(findTheDifference("", "y"));
//        System.out.println(findTheDifference("abwcd", "abcd"));
//        System.out.println(Arrays.toString(next("aabaaf")));

//        int[] ints = {0, 1, 0, 3, 12};
//        moveZeroes(ints);
//        System.out.println(Arrays.toString(ints));

//        System.out.println(Arrays.toString(plusOne(new int[]{9, 9, 9})));
//        System.out.println(Arrays.toString(plusOne(new int[]{1,2,3})));
//        System.out.println(Arrays.toString(plusOne(new int[]{0})));
//        System.out.println(Arrays.toString(plusOne(new int[]{9,8,7,6,5,4,3,2,1,0})));

//        System.out.println(arraySign(new int[]{-1, 1}));
//        System.out.println(arraySign(new int[]{-1,-2,-3,-4,3,2,1}));
//        System.out.println(arraySign(new int[]{1,5,0,2,-3}));
//        System.out.println(arraySign(new int[]{-1,1,-1,1,-1}));

//        System.out.println(isMonotonic(new int[]{1,2,2,3}));
//        System.out.println(isMonotonic(new int[]{6,5,4,4}));
//        System.out.println(isMonotonic(new int[]{1,3,2}));
//        System.out.println(isMonotonic(new int[]{2,2,2,3}));
//        System.out.println(isMonotonic(new int[]{2,2,2,2}));

        /*System.out.println(lengthOfLastWord("H"));
        System.out.println(lengthOfLastWord("Hxx"));
        System.out.println(lengthOfLastWord("Hello World"));
        System.out.println(lengthOfLastWord("H  fly me   to   the moon  "));
        System.out.println(lengthOfLastWord("luffy is still joyboy"));
        System.out.println(lengthOfLastWord("  W "));
        System.out.println(lengthOfLastWord("    "));
        System.out.println(lengthOfLastWord("Q    "));
        System.out.println(lengthOfLastWord("Q    Q"));
        System.out.println(lengthOfLastWord("    Q"));*/

        /*System.out.println(toLowerCase("H"));
        System.out.println(toLowerCase("Hello"));
        System.out.println(toLowerCase("LOVELY"));*/

        /*System.out.println(calPoints(new String[]{"5","2","C","D","+"}));
        System.out.println(calPoints(new String[]{"5","-2","4","C","D","9","+","+"}));*/

        /*System.out.println(judgeCircle("UD"));
        System.out.println(judgeCircle("LL"));*/

        /*System.out.println(tictactoe(new int[][]{{0,0},{2,0},{1,1},{2,1},{2,2}}));
        System.out.println(tictactoe(new int[][]{{0,0},{1,1},{0,1},{0,2},{1,0},{2,0}}));
        System.out.println(tictactoe(new int[][]{{0,0},{1,1},{2,2},{0,2},{1,0},{2,1}}));
        System.out.println(tictactoe(new int[][]{{0,0},{1,1},{2,0},{1,0},{1,2},{2,1},{0,1}, {0,2}, {2,2}}));
        System.out.println(tictactoe(new int[][]{{0,0},{1,1}}));*/

//        System.out.println(pivotIndex(new int[]{1, 7, 3, 6, 5, 6}));
//        System.out.println(pivotIndex(new int[]{1, 2, 3}));

//        System.out.println(searchInsert(new int[]{1, 3, 5, 6}, 5));
//        System.out.println(searchInsert(new int[]{1, 3, 5, 6}, 2));
//        System.out.println(searchInsert(new int[]{1, 3, 5, 6}, 7));
//        System.out.println(searchInsert(new int[]{1, 3}, 2));

//        char[] chars = {'h', 'e', 'l', 'l', 'o'};
//        reverseString(chars);
//        System.out.println(new String(chars));

//        Arrays.stream(twoSum(new int[]{2,7,11,15}, 9)).forEach(System.out::println);

//        System.out.println(removeElement(new int[]{3,2,2,3}, 3));
//        System.out.println(removeElement(new int[]{0,1,2,2,3,0,4,2}, 2));

//        System.out.println(findMaxConsecutiveOnes(new int[]{1,1,0,1,1,1}));
//        System.out.println(findMaxConsecutiveOnes(new int[]{1,0,1,1,0,1}));

//        int[] ints = {1, 2, 2, 1, 1, 0};
//        System.out.println(Arrays.toString(applyOperations(ints)));
//        System.out.println(Arrays.toString(applyOperations(new int[]{0,1})));

        /*int[] ints = {2,0,2,1,1,0};
        sortColors(ints);
        System.out.println(Arrays.toString(ints));
        ints = new int[]{2,0,1};
        sortColors(ints);
        System.out.println(Arrays.toString(ints));*/

        /*int[] ints = {1,2,3,4,5,6,7};
        rotate(ints, 3);
        System.out.println(Arrays.toString(ints));
        ints = new int[]{-1,-100,3,99};
        rotate(ints, 2);
        System.out.println(Arrays.toString(ints));*/

//        System.out.println(removeDuplicates(new int[]{1,1,1,2,2,3}));
//        System.out.println(removeDuplicates(new int[]{0,0,1,1,1,1,2,3,3}));

//        System.out.println(nthUglyNumber(10));

//        System.out.println(kSmallestPairs(new int[]{1,7,11}, new int[]{2,4,6}, 3));
//        System.out.println(kSmallestPairs(new int[]{1,1,2}, new int[]{1,2,3}, 2));

//        System.out.println(minNumBooths(new String[]{"acd","bed","accd"}));
//        System.out.println(minNumBooths(new String[]{"b","aaa","aaaaa","aaaaaa"}));

//        System.out.println(Arrays.toString(sortArrayByParity(new int[]{3,1,2,4})));
        /*System.out.println(10 & 0);
        System.out.println(10 & 1);
        System.out.println(9 & 0);
        System.out.println(9 & 1);*/

        /*int[][] ints = intervalIntersection(new int[][]{{0, 2}, {5, 10}, {13, 23}, {24, 25}}, new int[][]{{1, 5}, {8, 12}, {15, 24}, {25, 26}});
        for (int[] ints1 : ints) {
            System.out.println(Arrays.toString(ints1));
        }*/

//        System.out.println(kthSmallest(new int[][]{{1,3,11}, {2,4,6}}, 5));
//        System.out.println(kthSmallest(new int[][]{{1, 3, 5}, {2, 4, 6}, {0, 8, 9}}, 7));
//        System.out.println(kthSmallest(new int[][]{{1,10,10}, {1,4,5}, {2,3,6}}, 14));

        /*ListNode node = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4,
                new ListNode(5, new ListNode(6, new ListNode(3)))))));
        removeElements(node, 3).print();

        node = new ListNode(6, new ListNode(6, new ListNode(6, new ListNode(6,
                new ListNode(6, new ListNode(6, new ListNode(3)))))));
        removeElements(node, 6).print();*/

        /*ListNode node = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4,
                new ListNode(5, new ListNode(6, new ListNode(3)))))));

        reverseList(node).print();*/

        //["MyLinkedList","addAtHead","addAtTail","addAtIndex","get","deleteAtIndex","get"]
        // [[],[1],[3],[1,2],[1],[1],[1]]
        MyLinkedList list = new MyLinkedList();
        /*list.addAtHead(1);
        list.addAtTail(3);
        list.addAtIndex(1, 2);
        System.out.println(list.get(1));
        list.deleteAtIndex(1);
        System.out.println(list.get(1));*/

        //["MyLinkedList","addAtHead","addAtIndex","addAtTail","addAtHead","addAtIndex","addAtTail","addAtTail","addAtIndex","deleteAtIndex","deleteAtIndex","addAtTail"]
        // [[],[0],[1,4],[8],[5],[4,3],[0],[5],[6,3],[7],[5],[4]]
        /*list.addAtHead(0);
        list.addAtIndex(1, 4);
        list.addAtTail(8);
        list.addAtHead(5);
        list.addAtIndex(4, 3);
        list.addAtTail(0);
        list.addAtTail(5);
        list.addAtIndex(6, 3);
        list.deleteAtIndex(7);
        list.deleteAtIndex(5);
        list.addAtTail(5);*/

        //["MyLinkedList","addAtTail","addAtTail","get"]
        //[[],[1],[3],[1]]
        /*list.addAtTail(1);
        list.addAtTail(3);
        System.out.println(list.get(1));*/

//        System.out.println(swapPairs(ListNode.gene(new int[]{1,2,3,4})));
//        System.out.println(swapPairs(ListNode.gene(new int[]{1,2,3,4,5})));

//        System.out.println(deleteDuplicates(ListNode.gene(new int[]{1,1,2,3,3})));
//        System.out.println(deleteDuplicates_ii(ListNode.gene(new int[]{1, 2, 3, 3, 4, 4, 5})));
//        System.out.println(deleteDuplicates_ii(ListNode.gene(new int[]{1, 1, 1, 2, 3})));

//        System.out.println(mergeKLists(new ListNode[]{ListNode.gene(new int[]{1,4,5}), ListNode.gene(new int[]{1,3,4}), ListNode.gene(new int[]{2,6})}));

//        System.out.println(detectCycle(ListNode.gene(new int[]{3,2,0,-4}, 1)).val);
//        System.out.println(detectCycle(ListNode.gene(new int[]{1,2}, 0)).val);
//        System.out.println(detectCycle(ListNode.gene(new int[]{1,2}, 1)).val);

//        System.out.println(getIntersectionNode(ListNode.gene(new int[]{2,6,4}), ListNode.gene(new int[]{1,5})));

//        System.out.println(makeGood("leEeetcode"));

//        System.out.println(buildArray(new int[]{1, 3}, 3));
//        System.out.println(buildArray(new int[]{1, 2, 3}, 3));
//        System.out.println(buildArray(new int[]{1, 2}, 3));
//        System.out.println(buildArray(new int[]{2, 3, 4}, 4));

//        System.out.println(validateStackSequences(new int[]{1,2,3,4,5}, new int[]{4,5,3,2,1}));
//        System.out.println(validateStackSequences(new int[]{1,2,3,4,5}, new int[]{4,3,5,1,2}));
    }

    public static String removeDuplicateLetters(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        int[] lastIdx = new int[26];
        char[] cs = s.toCharArray();
        for (int i = 0; i < cs.length; i++) {
            lastIdx[cs[i] - 'a'] = i;
        }
        boolean[] visited = new boolean[26];
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < cs.length; i++) {
            int v = cs[i] - 'a';
            if (visited[v]) {
                continue;
            }
            while (!stack.isEmpty() && stack.peek() > cs[i] && lastIdx[stack.peek() - 'a'] > i) {
                visited[stack.pop() - 'a'] = false;
            }
            stack.push(cs[i]);
            visited[v] = true;
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }

    public static int[] nextGreaterElements(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        Deque<Integer> stack = new LinkedList<>();
        int nn = 2 * n - 1;
        for (int i = 0; i < nn; i++) {
            int curIdx = i % n;
            while (!stack.isEmpty() && nums[stack.peek()] < nums[curIdx]) {
                int idx = stack.pop();
                res[idx] = nums[curIdx];
            }
            stack.push(curIdx);
        }
        return res;
    }

    public static boolean validateStackSequences(int[] pushed, int[] popped) {
        if (pushed.length == 0 && popped.length == 0) {
            return true;
        }
        Deque<Integer> stack = new LinkedList<>();
        int j = 0;
        int n = pushed.length;
        for (int i = 0; i < n; i++) {
            stack.push(pushed[i]);
            while (!stack.isEmpty() && j < n && stack.peek() == popped[j]) {
                j++;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }

    public static List<String> buildArray(int[] target, int n) {
        if (target.length == 0) {
            return new ArrayList<>();
        }
        int i = 0;
        Deque<Integer> stack = new LinkedList<>();
        List<String> res = new ArrayList<>();
        while (i < target.length) {

            if (stack.isEmpty() || stack.peek() != target[i]) {
                int start = stack.isEmpty() ? 1 : stack.peek() + 1;
                while (start < target[i]) {
                    res.add("Push");
                    res.add("Pop");
                    start++;
                }
            }
            res.add("Push");
            stack.push(target[i]);
            i++;
        }
        return res;
    }

    /*public static String simplifyPath(String path) {

    }*/

    public static String makeGood(String s) {
        if (s.length() <= 1) {
            return s;
        }
        Deque<Character> stack = new LinkedList<>();
        for (char c : s.toCharArray()) {
            if (stack.isEmpty() || Math.abs(stack.peek() - c) != 32) {
                stack.push(c);
            } else {
                stack.pop();
            }
        }

        if (stack.isEmpty()) {
            return "";
        }

        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }

    static class MinStack {

        private Stack<Integer> stack;
        private Stack<Integer> minStack;

        public MinStack() {
            stack = new Stack<>();
            minStack = new Stack<>();
        }

        public void push(int val) {
            stack.push(val);
            if (minStack.isEmpty() || minStack.peek() >= val) {
                minStack.push(val);
            } else {
                minStack.push(minStack.peek());
            }
        }

        public void pop() {
            stack.pop();
            minStack.pop();
        }

        public int top() {
            return stack.peek();
        }

        public int getMin() {
            return minStack.peek();
        }
    }

    static class CustomStack {

        int[] arr;
        int size = 0;

        public CustomStack(int maxSize) {
            arr = new int[maxSize];
        }

        public void push(int x) {
            if (size >= arr.length) {
                return;
            }
            arr[size++] = x;
        }

        public int pop() {
            if (size == 0) {
                return -1;
            }
            return arr[--size];
        }

        public void increment(int k, int val) {
            k = Math.min(k, size);
            for (int i = 0; i < k; i++) {
                arr[i] += val;
            }
        }
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode a = headA;
        ListNode b = headB;
        while (a != b) {
            a = (a == null) ? headB : a.next;
            b = (b == null) ? headA : b.next;
        }
        return a;
    }

    public static ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head.next;
        ListNode fast = slow.next;
        while (fast != null && fast.next != null) {
            if (slow == fast) {
                ListNode cur = head;
                while (cur != slow) {
                    cur = cur.next;
                    slow = slow.next;
                }
                return slow;
            } else {
                slow = slow.next;
                fast = fast.next.next;
            }
        }
        return null;
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        PriorityQueue<ListNode> q = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
        for (ListNode list : lists) {
            if (list != null) {
                q.add(list);
            }
        }
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (!q.isEmpty()) {
            ListNode node = q.poll();
            cur.next = node;
            cur = cur.next;

            if (node.next != null) {
                q.add(node.next);
            }
        }
        return dummy.next;
    }

    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1 == null ? list2 : list1;
        return dummy.next;
    }

    public static ListNode deleteDuplicates_ii(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode();
        ListNode cur = head;

        ListNode nCur = dummy;

        while (cur != null) {
            ListNode post = next(cur);
            if (post == null) {
                break;
            }
            ListNode tmp = post.next;
            post.next = null;
            cur = tmp;
            nCur.next = post;
            nCur = nCur.next;
        }
        return dummy.next;
    }

    private static ListNode next(ListNode cur) {
        if (cur == null || cur.next == null) {
            return cur;
        }
        ListNode post = cur.next;
        int cnt = 1;
        while (post != null) {
            if (post.val != cur.val) {
                break;
            }
            cnt++;
            post = post.next;
        }
        if (cnt == 1) {
            return cur;
        }
        while (cnt > 0) {
            cur = cur.next;
            cnt--;
        }
        return next(cur);
    }

    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }

    public static ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode();
        ListNode nc = dummy;
        ListNode cur = head;
        ListNode post = head.next;
        while (cur != null && post != null) {

            //ListNode cTmp = cur.next;
            ListNode pTmp = post.next;
            cur.next = null;
            post.next = null;

            nc.next = post;
            nc = nc.next;
            nc.next = cur;
            nc = nc.next;

            cur = pTmp;
            post = cur == null ? null : cur.next;
        }
        if (post != null) {
            nc.next = post;
        }
        if (cur != null) {
            nc.next = cur;
        }
        return dummy.next;
    }


    static class MyLinkedList {

        ListNode head;
        ListNode tail;
        int size;

        public MyLinkedList() {
        }

        public int get(int index) {
            if (index < 0 || index >= size) {
                return -1;
            }
            ListNode cur = head;
            while (index-- > 0) {
                cur = cur.next;
            }
            return cur.val;
        }

        public void addAtHead(int val) {
            if (head == null) {
                head = new ListNode(val);
                tail = head;
            } else {
                head = new ListNode(val, head);
            }
            size++;
        }

        public void addAtTail(int val) {
            if (tail == null) {
                tail = new ListNode(val);
                head = tail;
            } else {
                tail.next = new ListNode(val);
                tail = tail.next;
            }
            size++;
        }

        public void addAtIndex(int index, int val) {
            if (index < 0 || index > size) {
                return;
            }
            if (index == 0) {
                addAtHead(val);
            } else if (index == size) {
                addAtTail(val);
            } else {
                ListNode cur = head;
                while (index-- > 1) {
                    cur = cur.next;
                }
                ListNode newNode = new ListNode(val, cur.next);
                cur.next = newNode;
                size++;
            }
        }

        public void deleteAtIndex(int index) {
            if (index < 0 || index >= size) {
                return;
            }
            if (index == 0) {
                head = head.next;
                if (size == 1) {
                    tail = null;
                }
            } else {
                ListNode cur = head;
                while (index-- > 1) {
                    cur = cur.next;
                }
                if (cur.next == tail) {
                    tail = cur;
                    cur.next = null;
                } else {
                    cur.next = cur.next.next;
                }
            }
            size--;
        }
    }

    public static ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode newHead = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;

            cur.next = newHead;
            newHead = cur;

            cur = next;
        }

        return newHead;
    }

    public static ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode();
        dummy.next = head;

        ListNode cur = dummy;
        while (cur != null && cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }

    public static List<Integer> targetIndices(int[] nums, int target) {
        if (nums.length == 0) {
            return new ArrayList<>();
        }
        List<Integer> ans = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                ans.add(i);
            }
        }
        return ans;
    }

    public static int[] getConcatenation(int[] nums) {
        if (nums.length == 0) {
            return nums;
        }
        int[] ans = new int[nums.length * 2];
        for (int i = 0; i < nums.length; i++) {
            ans[i] = ans[i + nums.length] = nums[i];
        }
        return ans;
    }

    public static int[] buildArray(int[] nums) {
        if (nums.length == 0) {
            return nums;
        }
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ans[i] = nums[nums[i]];
        }
        return ans;
    }

    public static int kthSmallest(int[][] mat, int k) {
        if (mat.length == 0) {
            return 0;
        }
        int[] a = mat[0];
        for (int i = 1; i < mat.length; i++) {
            a = kSmallestPair(a, mat[i], k);
        }
        return a[k - 1];
    }

    public static int[] kSmallestPair(int[] nums1, int[] nums2, int k) {

        PriorityQueue<int[]> p = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        int[] ans = new int[Math.min(k, nums1.length * nums2.length)];
        int idx = 0;
        p.add(new int[]{nums1[0] + nums2[0], 0, 0});

        while (!p.isEmpty() && idx < k) {
            int[] cur = p.poll();
            int i = cur[1];
            int j = cur[2];
            ans[idx++] = cur[0];

            if (j == 0 && i + 1 < nums1.length) {
                p.add(new int[]{nums1[i + 1] + nums2[j], i + 1, j});
            }
            if (j + 1 < nums2.length) {
                p.add(new int[]{nums1[i] + nums2[j + 1], i, j + 1});
            }
        }
        return ans;
    }

    public static int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        if (firstList.length == 0 || secondList.length == 0) {
            return new int[0][0];
        }

        List<int[]> ans = new ArrayList<>();
        int i = 0, j = 0;
        while (i < firstList.length && j < secondList.length) {
            int[] a = firstList[i];
            int[] b = secondList[j];
            int[] compare = compare(a, b);
            if (compare != null) {
                ans.add(compare);
            }
            if (a[1] < b[1]) {
                i++;
            } else {
                j++;
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }

    private static int[] compare(int[] a, int[] b) {
        if (a[0] > b[1] || b[0] > a[1]) {
            return null;
        }
        return new int[]{Math.max(a[0], b[0]), Math.min(a[1], b[1])};
    }

    public static int[] sortArrayByParity(int[] nums) {
        if (nums.length == 0) {
            return nums;
        }
        int i = 0, j = nums.length - 1;
        while (i < j) {
            if ((nums[i] & 1) == 1) {
                while (i < j && (nums[j] & 1) == 1) {
                    j--;
                }
                swap(nums, i, j);
                j--;
            }
            i++;
        }
        return nums;
    }

    public static int minNumBooths(String[] demand) {
        if (demand.length == 0) {
            return 0;
        }
        int[] count = new int[26];
        for (String s : demand) {
            cnt(count, s);
        }
        return Arrays.stream(count).sum();
    }

    private static void cnt(int[] count, String s) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            cnt[c - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            count[i] = Math.max(count[i], cnt[i]);
        }
    }

    public static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {

        PriorityQueue<int[]> p = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        List<List<Integer>> ans = new ArrayList<>();
        p.add(new int[]{nums1[0] + nums2[0], 0, 0});

        while (k > 0) {
            int[] cur = p.poll();
            int i = cur[1];
            int j = cur[2];
            ans.add(Arrays.asList(nums1[i], nums2[j]));
            if (j == 0 && i + 1 < nums1.length) {
                p.add(new int[]{nums1[i + 1] + nums2[j], i + 1, j});
            }
            if (j + 1 < nums2.length) {
                p.add(new int[]{nums1[i] + nums2[j + 1], i, j + 1});
            }
            k--;
        }
        return ans;
    }

    public static int nthUglyNumber(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return n;
        }
        int[] ans = new int[n + 1];
        ans[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; i++) {
            int a = ans[p2] * 2;
            int b = ans[p3] * 3;
            int c = ans[p5] * 5;
            int min = Math.min(a, Math.min(b, c));
            ans[i] = min;
            if (a == min) p2++;
            if (b == min) p3++;
            if (c == min) p5++;
        }
        return ans[n];
    }

    public static int[] shuffle(int[] nums, int n) {
        int[] ans = new int[n * 2];
        for (int i = 0; i < n; i++) {
            ans[i * 2] = nums[i];
            ans[i * 2 + 1] = nums[i + n];
        }
        return ans;
    }

    public static int removeDuplicates(int[] nums) {
        if (nums == null || nums.length <= 2) {
            return nums.length;
        }
        int p = 0, cnt = 1;
        int i = 1;
        while (i < nums.length) {
            if (nums[i] == nums[p]) {
                if (cnt < 2) {
                    nums[++p] = nums[i];
                    cnt++;
                }
            } else {
                nums[++p] = nums[i];
                cnt = 1;
            }
            i++;
        }
        return p + 1;
    }

    public static void rotate(int[] nums, int k) {
        if (nums == null || nums.length <= 1 || k == 0) {
            return;
        }
        int n = nums.length;
        k = k % n;
        reverse(nums, 0, n - k - 1);
        reverse(nums, n - k, n - 1);
        reverse(nums, 0, n - 1);

    }

    private static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }


    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


    public static void sortColors(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        int p = -1, q = 0, r = nums.length - 1;
        while (p < q && q <= r) {
            if (nums[q] == 0) {
                swap(nums, ++p, q++);
            } else if (nums[q] == 2) {
                swap(nums, q, r--);
            } else {
                q++;
            }
        }
    }


    public static int[] applyOperations(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }

        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                nums[i] *= 2;
                nums[i + 1] = 0;
            }
        }
        int i = 0, j = 0;
        while (i < n) {
            if (nums[i] != 0) {
                nums[j++] = nums[i];
            }
            i++;
        }
        while (j < n) {
            nums[j++] = 0;
        }
        return nums;
    }

    public static int findMaxConsecutiveOnes(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int sum = 0, ans = 0;
        /*for(int i = 0; i < nums.length; i++){
            if(nums[i] == 0){
                nums[i] = -1;
            }
        }*/
        for (int num : nums) {
            if (num > 0) {
                sum += num;
                ans = Math.max(sum, ans);
            } else {
                sum = 0;
            }
        }
        return ans;

    }

    public static int removeElement(int[] nums, int val) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int i = -1, j = 0;
        for (; j < nums.length; j++) {
            if (nums[j] != val) {
                nums[++i] = nums[j];
            }
        }
        return i + 1;
    }

    public static int[] twoSum(int[] numbers, int target) {
        if (numbers == null || numbers.length < 2) {
            return new int[]{0, 0};
        }
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int sum = numbers[i] + numbers[j];
            if (sum == target) {
                return new int[]{i + 1, j + 1};
            } else if (sum > target) {
                j--;
            } else {
                i++;
            }
        }
        return new int[]{-1, -1};
    }

    public static void reverseString(char[] s) {
        if (s == null || s.length <= 1) {
            return;
        }
        int left = 0, right = s.length - 1;
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }

    public static int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int left = 0, right = nums.length - 1;

        while (left + 1 < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (nums[right] < target) {
            return right + 1;
        }
        if (nums[left] >= target) {
            return left;
        }
        return right;
    }

    public static int pivotIndex(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int n = nums.length;
        int[] preSum = new int[n + 1];
        preSum[0] = 0;
        for (int i = 1; i <= n; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            if (preSum[i - 1] == preSum[n] - preSum[i]) {
                return i - 1;
            }
        }
        return -1;
    }

    public int diagonalSum(int[][] mat) {
        if (mat == null || mat.length == 0 || mat[0].length == 0) {
            return 0;
        }
        int sum = 0, n = mat.length;
        for (int i = 0; i < n; i++) {
            sum += mat[i][i];
            sum += mat[i][n - i - 1];
        }
        if (n % 2 == 1) {
            sum -= mat[n / 2][n / 2];
        }
        return sum;

    }

    public static int maximumWealth(int[][] accounts) {
        int ans = 0;
        for (int[] ints : accounts) {
            int sum = Arrays.stream(ints).sum();
            ans = Math.max(ans, sum);
        }
        return ans;
    }

    public static String tictactoe(int[][] moves) {
        if (moves == null || moves.length == 0) {
            return "Pending";
        }
        int n = moves.length;
        int[][] grid = new int[3][3];
        for (int i = 0; i < n; i++) {
            int x = moves[i][0], y = moves[i][1];
            grid[x][y] = i % 2 == 0 ? 1 : -1;
        }
        for (int i = 0; i < 3; i++) {
            if (grid[i][0] != 0 && grid[i][0] == grid[i][1] && grid[i][1] == grid[i][2]) {
                return grid[i][0] > 0 ? "A" : "B";
            }
            if (grid[0][i] != 0 && grid[0][i] == grid[1][i] && grid[1][i] == grid[2][i]) {
                return grid[0][i] > 0 ? "A" : "B";
            }

        }
        if (grid[0][0] != 0 && grid[0][0] == grid[1][1] && grid[1][1] == grid[2][2]) {
            return grid[0][0] > 0 ? "A" : "B";
        }
        if (grid[0][2] != 0 && grid[0][2] == grid[1][1] && grid[1][1] == grid[2][0]) {
            return grid[0][2] > 0 ? "A" : "B";
        }
        return n == 9 ? "Draw" : "Pending";
    }


    public static boolean judgeCircle(String moves) {
        if (moves == null || moves.isEmpty()) {
            return true;
        }
        int x = 0, y = 0;
        for (char c : moves.toCharArray()) {
            switch (c) {
                case 'U':
                    y++;
                    break;
                case 'D':
                    y--;
                    break;
                case 'L':
                    x--;
                    break;
                case 'R':
                    x++;
                    break;
            }
        }
        return x == 0 && y == 0;
    }

    public static int calPoints(String[] operations) {
        if (operations == null || operations.length == 0) {
            return 0;
        }
        List<Integer> ans = new ArrayList<>();
        for (String operation : operations) {
            switch (operation) {
                case "C":
                    ans.remove(ans.size() - 1);
                    break;
                case "D":
                    ans.add(ans.get(ans.size() - 1) * 2);
                    break;
                case "+":
                    ans.add(ans.get(ans.size() - 1) + ans.get(ans.size() - 2));
                    break;
                default:
                    ans.add(Integer.parseInt(operation));
            }
        }
        return ans.stream().mapToInt(Integer::intValue).sum();

    }

    public static String toLowerCase(String s) {
        if (s == null || s.isEmpty()) {
            return "";
        }
        char[] cs = s.toCharArray();
        for (int i = 0; i < cs.length; i++) {
            char c = cs[i];
            if (c >= A && c <= Z) {
                cs[i] = (char) (c + 32);
            }
        }
        return new String(cs);
    }

    static int A = 'A';
    static int Z = 'Z';

    public static int lengthOfLastWord(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int n = s.length();
        char[] cs = s.toCharArray();
        int i = n - 1;
        for (; i >= 0; i--) {
            if (cs[i] != ' ') {
                break;
            }
        }
        int j = i;
        for (; i >= 0; i--) {
            if (cs[i] == ' ') {
                return j - i;
            }
        }
        return j - i;
    }

    public static boolean isMonotonic(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return true;
        }
        int i = 1;
        int dir = (nums[nums.length - 1] >= nums[0]) ? 1 : -1;

        while (i < nums.length) {
            if (nums[i] > nums[i - 1] && dir == -1) {
                return false;
            }
            if (nums[i] < nums[i - 1] && dir == 1) {
                return false;
            }
            i++;
        }
        return true;
    }

    public static boolean canMakeArithmeticProgression(int[] arr) {

        if (arr == null || arr.length <= 2) {
            return true;
        }

        Arrays.sort(arr);
        int diff = arr[1] - arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] - arr[i - 1] != diff) {
                return false;
            }
        }
        return true;
    }

    public static int arraySign(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int sign = 1;
        for (int num : nums) {
            if (num == 0) {
                return 0;
            }
            if (num < 0) {
                sign *= -1;
            }
        }
        return sign;
    }

    public static int[] plusOne(int[] digits) {
        int len = digits.length;
        for (int i = len - 1; i >= 0; i--) {
            digits[i] = (digits[i] + 1) % 10;
            if (digits[i] != 0) {
                return digits;
            }
        }
        digits = new int[len + 1];
        digits[0] = 1;
        return digits;
    }

    public static int[] plusOne2(int[] digits) {
        if (digits == null || digits.length == 0) {
            return new int[]{};
        }
        int carry = 0;
        for (int i = digits.length - 1; i >= 0; i--) {
            int cur = i == digits.length - 1 ? digits[i] + 1 : digits[i] + carry;
            if (cur >= 10) {
                carry = 1;
                digits[i] = 0;
            } else {
                carry = 0;
                digits[i] = cur;
            }
        }
        if (carry == 1) {
            int[] newInts = new int[digits.length + 1];
            System.arraycopy(digits, 0, newInts, 1, digits.length);
            newInts[0] = 1;
            return newInts;
        }
        return digits;
    }

    public static void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[j++] = nums[i];
            }
        }
        while (j < nums.length) {
            nums[j] = 0;
            j++;
        }

    }

    public static int[] next(String str) {
        int[] next = new int[str.length()];
        int i = 1, j = 0;
        for (; i < str.length(); i++) {
            while (j > 0 && str.charAt(i) != str.charAt(j)) {
                j = next[j - 1];
            }
            if (str.charAt(i) == str.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }

    public static char findTheDifference(String s, String t) {
        int ret = 0;
        for (char c : s.toCharArray()) {
            ret ^= c;
        }
        for (char c : t.toCharArray()) {
            ret ^= c;
        }
        return (char) ret;

    }

    public static char findTheDifference2(String s, String t) {
        if (s == null || s.isEmpty()) {
            return t.charAt(0);
        }
        if (t == null || t.isEmpty()) {
            return s.charAt(0);
        }
        char[] cs = s.toCharArray();
        char[] ct = t.toCharArray();
        int[] map = new int[26];
        for (char c : cs) {
            map[c - 'a']++;
        }
        for (char c : ct) {
            map[c - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (map[i] != 0) {
                return (char) (i + 'a');
            }
        }
        return ' ';
    }

    public static String mergeAlternately(String word1, String word2) {
        if (word1 == null || word1.isEmpty()) {
            return word2;
        }
        if (word2 == null || word2.isEmpty()) {
            return word1;
        }

        StringBuilder sb = new StringBuilder();
        int i = 0, j = 0;
        while (i < word1.length() || j < word2.length()) {
            if (i < word1.length()) {
                sb.append(word1.charAt(i));
                i++;
            }
            if (j < word2.length()) {
                sb.append(word2.charAt(j));
                j++;
            }
        }
        return sb.toString();
    }

    public static int minSubArrayLen(int target, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int left = 0, right = 0;
        int sum = 0, ans = nums.length + 1;
        while (right < nums.length) {
            sum += nums[right];
            while (sum >= target) {
                ans = Math.min(ans, right - left + 1);
                sum -= nums[left];
                left++;
            }
            right++;
        }
        return ans == nums.length + 1 ? 0 : ans;
    }

    public static int minSubArrayLen2(int target, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        //int left = 0, right = 0;
        int sum = 0, ans = nums.length + 1;
        int i = 0, j = 0;
        while (i < nums.length) {
            while (sum < target && j < nums.length) {
                sum += nums[j++];
                if (sum >= target) {
                    ans = Math.min(ans, j - i);
                    break;
                }
            }
            sum -= nums[i++];
            if (sum >= target) {
                ans = Math.min(ans, j - i);
            }
        }
        return ans == nums.length + 1 ? 0 : ans;
    }
}
